/**
 * Created by zhourh on 2018/5/31.
 *
 * 给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
 *
 * 递归
 */
public class TrimBinarySearchTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(0);
        root.right = new TreeNode(2);
        System.out.println(TreeNode.treeNodeToString(new TrimBinarySearchTree().trimBST(root, 1, 2)));

        TreeNode root2 = new TreeNode(3);
        root2.left = new TreeNode(0);
        root2.right = new TreeNode(4);
        root2.left.right = new TreeNode(2);
        root2.left.right.left = new TreeNode(1);
        System.out.println(TreeNode.treeNodeToString(new TrimBinarySearchTree().trimBST(root2, 1, 3)));

    }

    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (L > R) {
            return null;
        }

        if (root == null) {
            return null;
        }

        if (root.val < L) {
            // 如果根节点的值比L还小，直接放弃其左子树
            return trimBST(root.right, L, R);
        }

        if (root.val > R) {
            // 如果根节点的值比L还大，直接放弃其右子树
            return trimBST(root.left, L, R);
        }

        // 根节点在取值范围内，保留根节点，分别修剪其左右子树
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);

        return root;
    }
}
